class Solution:
    def restoreIpAddresses(self, s: str) -> list:
        self.res = []
        self.diguichaxun(s, 1, [])
        return self.res

    def diguichaxun(self, s, index, list_in):
        if len(s) == 0:
            return
        if index == 4:
            if int(s) < 256 and (s[0] != "0" or s == "0"):
                self.res.append(".".join(list_in+[s]))
            return
        for i in range(1, 4):
            if int(s[:i]) < 256:
                self.diguichaxun(s[i:], index+1, list_in+[s[:i]])
                if s[:i] == "0":
                    break


a = Solution()
print(a.restoreIpAddresses("25525511135"))
print(a.restoreIpAddresses("100001"))